import os

# 输入和输出文件目录
input_dir = r'C:\Users\ASUS\Desktop\2024年新生赛出题\2024年新生赛出题(非大一组)\H题\H题_input'
output_dir = r'C:\Users\ASUS\Desktop\2024年新生赛出题\2024年新生赛出题(非大一组)\H题\H题_output'
os.makedirs(output_dir, exist_ok=True)

# 深度优先搜索算法用于查找“神秘之地”
def dfs(grid, visited, x, y):
    stack = [(x, y)]
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    visited[x][y] = True
    
    while stack:
        cx, cy = stack.pop()
        for dx, dy in directions:
            nx, ny = cx + dx, cy + dy
            if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and not visited[nx][ny] and grid[nx][ny] == '1':
                visited[nx][ny] = True
                stack.append((nx, ny))

# 计算“神秘之地”的数量
def num_islands(grid):
    if not grid:
        return 0
    m, n = len(grid), len(grid[0])
    visited = [[False] * n for _ in range(m)]
    count = 0
    
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1' and not visited[i][j]:
                dfs(grid, visited, i, j)
                count += 1
                
    return count

# 处理每个输入文件并生成对应的输出文件
for filename in os.listdir(input_dir):
    if filename.endswith('.in'):
        input_path = os.path.join(input_dir, filename)
        output_path = os.path.join(output_dir, filename.replace('.in', '.out'))

        # 读取输入文件
        with open(input_path, 'r') as f:
            m, n = map(int, f.readline().strip().split())
            grid = [list(f.readline().strip()) for _ in range(n)]

        # 计算结果
        result = num_islands(grid)

        # 写入输出文件
        with open(output_path, 'w') as f:
            f.write(f"{result}\n")

print("所有 .out 文件已生成并保存在指定目录中。")
